/*
============================================================================
 Name        : dd_vector.c
 Author      : Jian (raphyer@hotmail.com)
 Version     :
 Copyright   : GPL
 Description : dd_vector.c - source file
============================================================================
*/

/* INCLUDE FILES */
#include "dd_vector.h"
#include "dd_log.h"

#define __DD_DEFAULT_VEC_SIZE	8 

static void _expand_to(dd_vector* vec, int size)
{
	if ( vec && vec->count < size ) {
		void** pre_ptr = vec->ptr ;
		vec->ptr = (void**)dd_malloc(size * sizeof(void*)) ;
		memcpy( vec->ptr, pre_ptr, vec->count * sizeof(void*) ) ;
		vec->allocSize = size ;
		dd_destroy(pre_ptr) ;
	}
}


dd_vector* dd_vector_create(int granularity) 
{
	dd_vector* vec		= (dd_vector*)dd_malloc(sizeof(dd_vector)) ;
    
    __DD_CHECK_MEM(vec, sizeof(dd_vector), return NULL) ;

	vec->granularity	= (granularity > 0) ? granularity : __DD_DEFAULT_VEC_SIZE ;
	vec->ptr			= (void**)dd_malloc(vec->granularity * sizeof(void*)) ;
	vec->count			= 0 ;
	vec->allocSize		= vec->granularity ;
	return vec ;
}

void dd_vector_destroy(dd_vector* vec, void (*free_fun)(void*)) 
{
	if(vec) {
		if (free_fun)
			dd_vector_reset(vec, free_fun) ;

		if(vec->ptr) 
			dd_destroy(vec->ptr) ;

		dd_destroy(vec) ;
	}
}

int dd_vector_count(const dd_vector* vec) 
{
    return vec ? vec->count : 0 ;
}

void* dd_vector_get(const dd_vector* vec, DD_UINT index) 
{
    __DD_ASSERT_DEFENSE(vec && index < vec->count, return NULL) ;

	return *(vec->ptr + index) ;
}

void dd_vector_set(dd_vector* vec, DD_UINT index, void* data)
{
    __DD_ASSERT_DEFENSE(vec && index < vec->count, return) ;

	*(vec->ptr + index) = data ;
}

void dd_vector_append(dd_vector* vec, void* data) 
{
	if (vec->count == vec->allocSize) 
		_expand_to(vec, vec->count + vec->granularity) ;

	vec->count++ ;
	dd_vector_set(vec, vec->count - 1, data) ;
}

void dd_vector_insert(dd_vector* vec, DD_UINT insertIndex, void* data) 
{
    __DD_ASSERT_DEFENSE(vec && insertIndex <= vec->count, return) ;

	if ( vec->count == vec->allocSize ) 
		_expand_to( vec, vec->count + vec->granularity ) ;

	if ( insertIndex >= vec->count ) {
		vec->count++ ;
		dd_vector_set( vec, vec->count - 1, data ) ;
	}
	else {
		memmove(vec->ptr + insertIndex + 1, vec->ptr + insertIndex, (vec->count - insertIndex) * sizeof(void*));
		*(vec->ptr + insertIndex) = data ;
		vec->count++ ;
	}
}

void dd_vector_expand(dd_vector* vec, int expandSize) 
{
	int newSize = vec->count + expandSize ;

	if ( newSize > vec->allocSize )
		_expand_to( vec, newSize ) ;

	vec->count += expandSize ;
}

void dd_vector_reset(dd_vector* vec, void (*free_fun)(void*)) 
{
	if ( vec->count != 0 && free_fun ) {
		int i = 0 ; 
		for ( ; i < vec->count; i++ )
			free_fun(dd_vector_get(vec, i)) ;
	}

	vec->count = 0 ;
}


int dd_vector_find(dd_vector* vec, void* data) 
{
	int i = 0 ;
	for ( ; i < vec->count; i++ ) {
		if ( data == dd_vector_get( vec, i) )
			return i ;
	}

	return -1 ;
}

void* dd_vector_delete_by_index(dd_vector* vec, DD_UINT index)
{
	void* delElement = NULL ;
    
    __DD_ASSERT_DEFENSE(vec && index < vec->count, return NULL) ;

    delElement = *(vec->ptr + index) ;
    *(vec->ptr + index) = NULL;
    memmove(vec->ptr + index, vec->ptr + index + 1, (vec->count - (index + 1)) * sizeof(void*));
    *(vec->ptr + vec->count - 1) = NULL;
    vec->count-- ;

	return delElement ;
}

void* dd_vector_delete(dd_vector* vec, void* data)
{
	int index = dd_vector_find(vec, data) ;
	
	if ( index == -1 )
		return NULL ;

	return dd_vector_delete_by_index(vec, index) ;
}


void dd_vector_swap(dd_vector* vec, DD_UINT index1, DD_UINT index2) 
{
    void* tmp = NULL ;

    __DD_ASSERT_DEFENSE(vec && index1 < (DD_UINT)vec->count && index2 < (DD_UINT)vec->count, return) ;

    tmp = *(vec->ptr + index1);
    *(vec->ptr + index1) = *(vec->ptr + index2) ;
    *(vec->ptr + index2) = tmp ;
}


void dd_vector_insert_by(dd_vector* vec, void* data, dd_vector_data_cmp* compare) 
{   
    if (vec && compare) {

        int start = 0 ;
        int end   = dd_vector_count(vec) - 1 ;
        int mid   = 0 ;
        int cmp   = -1 ;
        
        while(start <= end) {
            
            mid = start + (end - start) / 2 ;
            
            cmp = compare(data, dd_vector_get(vec, mid)) ; 
            
            if (cmp == 0) {
                dd_vector_insert(vec, mid, data) ;
                return ;
            }
            
            if (cmp < 0)
                end = mid - 1 ;
            else 
                start = mid + 1 ;
            
        }
        
        __DD_ASSERT((start == end + 1) && (end < dd_vector_count(vec))) ;
        
        if (cmp < 0) 
            dd_vector_insert(vec, mid, data) ;
        else 
        dd_vector_insert(vec, mid + 1, data) ; 
    }
}

static int _find_sorted_vec_by_key(const dd_vector* vec, const void* key, dd_vector_key_cmp* compare)
{
    if (vec && compare) {

        int start = 0 ;
        int end   = dd_vector_count(vec) - 1 ;
        int mid   = 0 ;
        int cmp   = -1 ;

        while(start <= end) {

            mid = start + (end - start) / 2 ;

            cmp = compare(key, dd_vector_get(vec, mid)) ; 

            if (cmp == 0)
                return mid ;

            if (cmp < 0)
                end = mid - 1 ;
            else 
                start = mid + 1 ;
        }
    }

    return -1 ;
}

int dd_vector_find_by_key(const dd_vector* vec, const void* key, dd_vector_key_cmp* compare, int isSort)
{
    int i = 0 ;

    if (isSort) 
        return _find_sorted_vec_by_key(vec, key, compare) ;
    
    for (; i < dd_vector_count(vec); i++) {
        if (compare(key, dd_vector_get(vec, i)) == 0)
            return i ;
    }

    return -1 ;
}

void* dd_vector_delete_by_key(dd_vector* vec, const void* key, dd_vector_key_cmp* compare, int isSort) 
{
    int findex = dd_vector_find_by_key(vec, key, compare, isSort) ;

    if (findex != -1)
        return dd_vector_delete_by_index(vec, findex) ;

    return NULL ;
}


void dd_vector_sort(dd_vector* vec, dd_vector_data_cmp* compare) 
{
    if ( vec && (vec->count > 1) && compare ) {
        int count = vec->count ;
        int i = 0 ;  
        void* data = NULL ;
        
        vec->count =  0 ;
        
        for (; i < count; i++) {
            data = dd_vector_getfast(vec, i) ;
            dd_vector_insert_by(vec, data, compare) ;
        }
        
        __DD_ASSERT(vec->count == count) ;
    }
}


#ifdef __DD_TEST

#include "sd_platform.h"

#define __TEST_APPEND_TIMES		2000
#define __TEST_INSERT_INDEX		1500
#define __TEST_INSERT_TIMES		1000

#define __TEST_INSERT_BY_TIMES  (10000 + 1)


static int _ut_compare(const void* data1, const void* data2)
{
    int val1 = (int)data1 ;
    int val2 = (int)data2 ;
    
    if (val1 == val2)  return 0 ;
    
    if (val1 < val2)  return -1 ;
        
    return 1 ;
}

static int _ut_compare_ptr(const void* data1, const void* data2)
{
    int val1 = *((int*)data1) ;
    int val2 = *((int*)data2) ;
    
    if (val1 == val2)  return 0 ;
    
    if (val1 < val2)  return -1 ;
    
    return 1 ;
}

static DD_BOOL _ut_check_sorted_vec(const dd_vector* vec, int (*compare)(const void*, const void*)) 
{
    int i = 0 ;
    for (; i < dd_vector_count(vec) - 1; i++){
        
        if (compare(dd_vector_get(vec, i), dd_vector_get(vec, i+1)) > 0)
            return DD_FALSE ;
    }

    return DD_TRUE ;
}


DD_BOOL dd_vector_test() 
{
	dd_vector* vec = dd_vector_create(10) ;
    dd_vector* sorted_vec = dd_vector_create(10) ;
	int i = 0 ;
	int insertIndex = __TEST_INSERT_INDEX;
	int del_count	= 0 ;

	/* Test append */
	for ( ; i < __TEST_APPEND_TIMES; i++ ) {
		int* tmp = dd_malloc(sizeof(int)) ;
		*tmp = i ;
		dd_vector_append(vec, tmp) ;
	}

	if ( dd_vector_count(vec) != __TEST_APPEND_TIMES )
		return DD_FALSE ;

	for ( i = 0 ; i < __TEST_APPEND_TIMES ; i++ ) {
		int tmp = *((int*)(dd_vector_get(vec, i))) ;
		if ( tmp != i )
			return DD_FALSE ;
	}

	/* Test insert */
	for ( i = 0; i < __TEST_INSERT_TIMES; i++ ) {
		int* tmp = dd_malloc(sizeof(int)) ;
		*tmp = __TEST_INSERT_TIMES + i ;
		dd_vector_insert(vec, insertIndex, tmp);
		insertIndex++ ;
	}

	if ( dd_vector_count(vec) != (__TEST_INSERT_TIMES + __TEST_APPEND_TIMES) )
		return DD_FALSE ;

	insertIndex = __TEST_INSERT_INDEX; 
	for ( i = 0 ; i < insertIndex ; i++ ) {
		int tmp = *((int*)(dd_vector_get(vec, i))) ;
		if ( tmp != i )
			return DD_FALSE ;
	}

	for ( ; i < (insertIndex + __TEST_INSERT_TIMES); i++ ) {
		int tmp = *((int*)(dd_vector_get(vec, i))) ;
		if ( tmp != __TEST_INSERT_TIMES + (i - insertIndex) )
			return DD_FALSE ;
	}
	
	for ( ; i < __TEST_INSERT_TIMES + __TEST_APPEND_TIMES; i++ ) {
		int tmp = *((int*)(dd_vector_get(vec, i))) ;
		if ( tmp != i - __TEST_INSERT_TIMES )
			return DD_FALSE ;
	}

	/* Test Delete */
	srand((DD_UINT)time(0)) ;
	for (i = 0 ;i < dd_vector_count(vec); i++) {
		if (rand() % 3 == 0) {
			dd_vector_delete_by_index(vec, i) ;
			del_count++ ;
		}
	}

	if ( dd_vector_count(vec) != (__TEST_INSERT_TIMES + __TEST_APPEND_TIMES - del_count) )
		return DD_FALSE ;

    dd_vector_reset(vec, dd_free) ;
    
    i = 0 ;
    srand((DD_UINT)time(0)) ;
    for (; i < __TEST_INSERT_BY_TIMES; i++) {
        int* tmp = dd_malloc(sizeof(int)) ;
		*tmp =  rand() ;
        dd_vector_append(vec, (void*)tmp) ;

        dd_vector_insert_by(sorted_vec, (void*)(*tmp), _ut_compare) ;

        if (!_ut_check_sorted_vec(sorted_vec, _ut_compare)) 
            return DD_FALSE ;
    }
    
    i = 0 ;
    for (; i < __TEST_INSERT_BY_TIMES; i++) {
        int* tmp   = (int*)dd_vector_get(vec, i) ;
        int findex = dd_vector_find_by_key(sorted_vec, (void*)(*tmp), _ut_compare, 1) ;
        
        if (findex == -1 || *tmp != (int)dd_vector_get(sorted_vec, findex))
            return DD_FALSE ;
    }

    dd_vector_sort(vec, _ut_compare_ptr) ;

    if (!_ut_check_sorted_vec(vec, _ut_compare_ptr))
            return DD_FALSE ;

    i = 0 ;
    for (; i < __TEST_INSERT_BY_TIMES; i++) {
        int* tmp   = (int*)dd_vector_get(vec, i) ;
        if (*tmp != (int)dd_vector_get(sorted_vec, i))
            return DD_FALSE ;
    }


	dd_vector_destroy(vec, dd_free) ;
    dd_vector_destroy(sorted_vec, NULL) ;

	return DD_TRUE ;
}


void dd_vector_dump_file(const dd_vector* vec, const char* file_name) 
{
    sd_file* file = sd_file_open((const DD_UTF8*)file_name, DD_FILE_REPLACE) ;

    sd_file_write(file, vec, sizeof(dd_vector)) ;

    sd_file_write(file, vec->ptr, vec->count * sizeof(void*)) ;

    sd_file_close(file) ;
}

dd_vector* dd_vector_read_file(const char* file_name) 
{
    dd_vector* vec =  dd_vector_create(5) ;
    
    sd_file* file = sd_file_open((const DD_UTF8*)file_name, DD_FILE_READ) ;
    
    dd_free(vec->ptr) ;

    sd_file_read(file, vec, sizeof(dd_vector)) ;

    vec->ptr = (void**)dd_malloc(vec->allocSize * sizeof(void*)) ;

    sd_file_read(file, vec->ptr, vec->count * sizeof(void*)) ;

    sd_file_close(file) ;

    return vec ;
}

#endif	/* __DD_TEST */


/* End of File */
